Được chọn là thủ đô của vương triều mới, Idris I đã chọn xây dựng một thị trấn mới nằm bên bờ phải của sông Fes vào năm 789 sau công nguyên. Nhiều cư dân đầu tiên của thị trấn này là những người tị nạn trốn chạy trong cuộc nổi dậy ở Córdoba (Tây Ban Nha ngày nay).[4] Tuy nhiên, vào năm 809, con trai của ông là Idris II đã quyết định chọn kinh đô của mình nằm ở phía đối diện bờ sông Fes. Vẫn có nhiều người tị nạn quyết định định cư ở thị trấn mới đó, nhưng đó là những người tị nạn trong cuộc nổi dậy ở Kairouan (Tunisia ngày nay).[4] Mặc dù chỉ ngăn cách bởi con sông nhưng hai thị trấn này phát triển riêng biệt cho đến thế kỷ 11, khi chúng được thống nhất thành một bởi Triều đại Almoravid.

Một ví dụ điển hình về cách những người tị nạn góp phần làm cho Fes phát triển mạnh mẽ trong những năm đầu là trường đại học Al-Karaouine được xây dựng bởi một người tị nạn Tunisia vào năm 859. Nó được coi là trường đại học lâu đời nhất thế giới.[1] Dưới thời Almoravid, Fes mất dần vị thế của một thủ đô khi Almoravid tạo ra Marrakech, nơi được chọn là thủ đô mới của triều đại. Vào thời kỳ này, một phần lớn của Fes el Bali bị phá hủy nhưng đã tạo ra Fes hiện đại khi hợp nhất hai thị trấn bằng cách phá hủy ngăn cách và xây các cây cầu bắc qua sông Fes.

Đến triều đại Khalip Almohad, Fes là một thành phố buôn bán thịnh vượng mặc dù không phải là một thủ đô, và thậm chí dần trở thành thành phố lớn nhất thế giới với 200.000 cư dân ở đó.[5]

Sau khi đánh bại nhà Almoravid ở Maroc, Triều đại Marinid đã rời đô từ Marrakech về Fes.[6] Điều này đánh dấu sự khởi đầu của thời kỳ vĩ đại nhất trong lịch sử đối với Fes el Bali.[6] Khi Marinid rời đô về Fes vào năm 1276, họ bắt đầu xây dựng một thị trấn mới bên ngoài các bức tường thành. Lúc đầu, nó được gọi là Thành phố Trắng,[6] nhưng sau một thời gian nó được gọi với tên là Fes Jdid hay New Fes. Hầu hết các di tích chính ở Fes el Bali được xây dựng dưới thời cai trị của Marinid. Vào thế kỷ 14, một nghĩa trang Do Thái đã được xây dựng tại khu vực đô thị của Fes cổ.